#include "dpalgo.h"
#include "string.h"

int DPSubSetSum(DataSet &ds) {
	int n, u, cnt, cur, res;
	n = ds.n;
	u = ds.u;

	int *dp = (int *)malloc(sizeof(int) * (u + 1));
	memset(dp, 0, sizeof(int) * (u + 1));

	for (cnt = 0; cnt < n; ++cnt)
		for (cur = u; cur >= (ds.nums)[cnt]; --cur)
			if (dp[cur] < dp[cur - (ds.nums)[cnt]] + (ds.nums)[cnt])
				dp[cur] = dp[cur - (ds.nums)[cnt]] + (ds.nums)[cnt];

	res = dp[u];
	free(dp);
	return res;
}